215. Kth Largest Element in an Array

Medium

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

1. using Priority Queue

   Notice: priority queue is increase order

from queue import PriorityQueue
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if not nums: return None
        pq = PriorityQueue()
        for i in nums:
            pq.put(-i)
        for _ in range(k-1):
            pq.get()
        return -pq.get()

Time complexity: O(n log n) insert a element O(log n)

Space complexity: O(n)

我们也可以发现这题本质其实是考察排序，所以有如下一些排序方法

This question ask you to find the kth largest element in the list appearly, but actually it wants you to use different sorted algorithm

2. Sorted (off the shelf)

   Timsort algoritm, 结合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[::-1][k-1]

Time complexity: O(n log n) because using Timsort

Space complexity: O(n)

3. Bubble sorted

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        for i in range(k):
          # keep moving large element to the end
            for j in range(len(nums)-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return nums[len(nums) - k]

Time complexity: O(n k)

Space complexity: O(n)